package sort;

import java.util.*;

import org.junit.Test;

public class Ex406 {
    class Solution {
        public int[][] reconstructQueue(int[][] people) {

            Arrays.sort(people, (o1, o2) -> o2[0] - o1[0]);
            Arrays.sort(people, (o1, o2) -> {
                if (o1[0] == o2[0]) return o1[1] - o2[1];
                else return 0;
            });

            for (int i = 0; i < people.length; i++) {
                int t = people[i][1];
                if (t < i) {
                    //前面都是大于等于当前元素的，因此他们并不会在意比他小的元素的介入
                    moveAndSwap(people, t, i);
                }
            }

            return people;
        }
        //i < j, 将i及其之后到j-1的部分后移一位，并将i位置放上j元素
        public void moveAndSwap(int[][] nums, int i, int j) {
            int[] temp = nums[j];
            for (int k = j; k > i; k--) {
                nums[k] = nums[k - 1];
            }
            nums[i] = temp;
        }
    }

    @Test
    public void test() {
        int[][] nums = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
        Solution s = new Solution();
        s.reconstructQueue(nums);

        for (int i = 0; i < nums.length; i++) {
            System.out.println(Arrays.toString(nums[i]));
        }
    }
}
